//1.二分-山脉数组的峰顶索引
//二段性:
//arr[mid] < arr[mid + 1], 峰值在mid右侧 
//arr[mid] > arr[mid + 1], 峰值是mid或在mid左侧
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(arr[mid] < arr[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

//2.二分-寻找峰值
//二段性:
//nums[i] > nums[i + 1], 左侧一定存在峰值
//nums[i] < nums[i + 1], 右侧一定存在峰值
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};
